package com.cn.algorithm02.class18;

import java.util.*;

/***
 * @author: hels
 * @description: 字符串打印所有的子序列
 **/
public class C02_PrintAllSubSequences {
    // 打印所有的子序列
    public static void sub(String arr) {
        char[] chars = arr.toCharArray();
        ArrayList<String> ans = new ArrayList<>();
        process1(chars, 0, ans, "");
        System.out.println(ans);
    }

    private static void process1(char[] chars, int index, ArrayList<String> ans, String path) {
        if (index == chars.length) {
            ans.add(path);
            return;
        }
        // index游标到当前位置，该字符要或者不要？
        String yes = path + String.valueOf(chars[index]);
        process1(chars, index+1, ans, yes);
        String no = path;
        process1(chars, index+1, ans, no);
    }

    // 打印所有的子序列，需要去重
    public static void sub2(String arr) {
        char[] chars = arr.toCharArray();
        Set<String> ans = new HashSet<>();
        process2(chars, 0, ans, "");
        System.out.println(ans);
    }

    private static void process2(char[] chars, int index, Set<String> ans, String path) {
        if (index == chars.length) {
            ans.add(path);
            return;
        }
        // index游标到当前位置，该字符要或者不要？
        String yes = path + String.valueOf(chars[index]);
        process2(chars, index+1, ans, yes);
        String no = path;
        process2(chars, index+1, ans, no);
    }


    public static void main(String[] args) {
        sub("abc");
        System.out.println("-----");
        sub("accc");
        System.out.println("-----");
        sub2("accc");
    }
}
